\setcounter{listing}{0}
\chapter{栈和队列的应用}
\section{实验目的}
\begin{itemize}
  \item 通过本次实验进一步加深对栈和队列的理解,在此基础上实现顺序栈、链式栈、顺序队列、链式队列的表示方法。
  \item 掌握循栈和队列的基本操作(包括:创建、进栈、出栈、入队、出队等基本操作)。
  \item 在掌握基本操作的基础上,对实验给出的扩展实验题目进行分析、建模。
  \item 在栈或队列的基础上构造相应的算法解决问题。
\end{itemize}

\section{基础实验题目}
本次实验分别给出了栈和队列的顺序、链式定义及操作接口声明，读者可以选择如下内容完成实验：
\begin{itemize}
  \item 顺序栈 + 链式队列
  \item 链式栈 + 顺序队列
\end{itemize}

\subsection{栈的结构定义及操作接口实现}
\label{sec:stack}

以下分别给出栈的顺序及链式定义以及操作接口，读者可自行选择其中一类实现方式。
\subsubsection{栈的顺序实现}
在代码\ref{lstseqstack}描述栈的顺序实现中，我们定义的\lstinline{struct stStack;}结构体包括4个成员：
\begin{description}
  \item[POSITION top] 指向栈顶，由于定义了栈底为\lstinline{#define BUTTOM -1}，需要考虑在初始化栈时，栈顶\textbf{top}指针应为\lstinline{top = BUTTOM}。
  \item[ELEMTYPE *buffer] 指向为顺序栈开辟的连续存储空间首地址。
  \item[SIZE\_T MAXNUM] 表示顺序栈所能容纳的元素个数。
  \item[SIZE\_T length] 表示栈当前包含的元素个数(长度)。
\end{description}

\label{sec:seqstack}

\captionof{listing}{顺序栈数据结构定义及操作接口声明}
\label{lstseqstack}
\begin{minted}[linenos, frame=single]{c}
typedef int POSITION;
typedef int SIZE_T;
typedef char ELEMTYPE;

#define BUTTOM -1

struct stStack {
  POSITION top;
  ELEMTYPE *buffer;
  SIZE_T MAXNUM;
  SIZE_T length;
};
typedef struct stStack *PSeqStack;
  
PSeqStack createEmptyStack(int m);
int destroy(PSeqStack *pstack);

//清空栈元素
int clear(PSeqStack *pstack);

int isEmpty(PSeqStack pstack);
int isFull(PSeqStack pstack);

int push(PSeqStack pstack, ELEMTYPE x);
int pop(PSeqStack pstack);
int top(PSeqStack pstack, ELEMTYPE *x);

SIZE_T size(PSeqStack pstack);
int empty(PSeqStack pstack);

int printStack(PSeqStack pstack);
\end{mitned}

\subsubsection{栈的链式实现}
\label{sec:lnstack}

如代码\ref{lstlnstack}所示栈的链式表示中，使用\lstinline{struct Node}结构体表示链式栈中的结点元素。
链式栈中需要考虑的一点便是如何表示链式栈为空，从代码\ref{lstlnstack}可知，表示栈空可以由如下两种形式：
\begin{itemize}
  \item \textbf{top} == \textbf{NULL}
  \item \textbf{length} == 0
\end{itemize}

\captionof{listing}{链式栈数据结构定义及操作接口声明}
\label{lstlnstack}
\begin{minted}[linenos, frame=single]{c}
typedef char ELEMETYPE;
struct Node;
typedef struct Node *PNode;

struct Node {
  ELEMTYPE info;
  PNode link;
};

struct stStack {
  PNode top;
  SIZE_T length;
};

typdef struct stStack *PLStack;

PLStack createEmptyStack();
int destroy(PLStack *pstack);

int print(PLStack pstack);
int clear(PLStack pstack);

int push(PLStack pstack, ELEMTYPE x);
int pop(PLStack pstack);
int top(PLStack pstack, ELEMTYPE *x);

int isEmpty(PLStack pstack);
int isFull(PLStack pstack);

int size(PLStack pstack);
int empty(PLStack pstack);
\end{minted}

\subsection{测试题目：栈}
\label{sec:stacktest}
完成第\ref{sec:seqstack}及\ref{sec:lnstack}节所示的栈顺序或链式实现后，请使用如下题目对你的代码进行测试。

\subsubsection*{问题描述}
这是一个简单的堆栈操作模拟问题，你需要模拟出堆栈的基本操作（包括入栈、出栈、取栈顶等），操作命令包含如下格式：
\begin{description}
  \item[CREATE m] 创建一个最多可存储$m$个元素的堆栈；
  \item[DESTROY]  销毁堆栈，堆栈一旦销毁便无法再进行其他操作；
  \item[SIZE]     在一行中输出栈当前包含的元素个数；
  \item[PUSH x]   将$x$入栈，其中$x$为char类型
  \item[POP]      栈顶元素出栈；
  \item[PRINTALL] 在一行中打印栈中所有元素，最左侧为栈底元素，最右侧为栈顶元素，每个元素之间有一个空格；如果栈中无元素则输出NULL；
  \item[PRINTTOP] 在一行中打印栈顶元素；如果栈中无元素则输出NULL；
  \item[CLEAR]    清空栈中所有元素；
  \item[STOP]     终止执行命令序列；
\end{description}

\subsubsection*{输入数据格式}
输入包含多行，每行包含一个合法的命令；遇到\textbf{STOP}则结束。我们确保$m$的不超过1000，且命令数量不超过2000条。

\subsubsection*{输出数据格式}
对于每一个命令，模拟堆栈操作。对于有输出要求的命令，请按照命令的输出格式将数据输出。

\subsubsection*{输入样例}
\begin{lstlisting}[frame=none, numbers=none]
CREATE 10
PUSH a
PUSH b
PUSH c
PRINTALL
SIZE
PRINTTOP
POP
PUSH 1
PRINTALL
DESTROY
CREATE 20
PUSH a
PUSH b
PUSH c
PUSH d
CLEAR
PUSH e
PUSH f
PUSH g
POP
POP
POP
PUSH 1
PUSH 2
PRINTALL
DESTROY
STOP
\end{lstlisting}

\subsubsection*{输出样例}

\begin{lstlisting}[frame=none, numbers=none]
a b c
3
c
1 b a
NULL
2
1 2
\end{lstlisting}

\subsection{队列的结构定义及操作接口实现}
\label{sec:queue}

以下分别给出队列的顺序及链式定义以及操作接口声明，读者可自行选择其中一类实现方式。

\subsubsection{队列的顺序实现}
\label{sec:seqqueue}

\captionof{listing}{顺序队列数据结构定义及操作接口声明}
\label{lstseqqueue}
\begin{minted}[linenos, frame=single]{c}
typedef int POSITION;
typedef int SIZE_T;
typedef char ELEMTYPE;

struct stQueue {
  SIZE_T MAXNUM;
  SIZE_T length;
  ELEMTYPE *buffer;
  POSITION head, rear;
};
  
typedef struct stQueue * Psqueue;
  
Psqueue createEmptyQueue(int num);
int destroy(Psqueue *queue);

int enqueue(Psqueue queue, ELEMTYPE x);
int dequeue(Psqueue queue);

int front(Psqueue queue, ELEMTYPE *x);
int clear(Psqueue queue);
int size(Psqueue queue);

int isEmpty(Psqueue queue);
int isFull(Psqueue queue);

int printQueue(Psqueue queue);
\end{minted}

\subsubsection{队列的链式实现}
\label{sec:lnqueue}

\captionof{listing}{链式队列数据结构定义及操作接口声明}
\label{lstlnqueue}
\begin{minted}[linenos, frame=single]{c}
typedef char ELEMTYPE;
struct Node;
typedef struct Node * PNode;

struct Node {
  ELEMTYPE info;
  PNode link;
};

struct stQueue {
  PNode head;
  PNode rear;
  SIZE_T length;
};

typedef struct stQueue * PLQueue;

PLQueue createQueue();
int destroy(PLQueue *queue);
int clear(PLQueue queue);

int enqueue(PLQueue queue, ELEMTYPE x);
int dequeue(PLQueue queue);
int front(PLQueue queue, ELEMTYPE *x);

int size(PLQueue queue);
int print(PLQueue queue);
\end{minted}

\subsection{测试题目：队列}

\subsubsection*{问题描述}
这是一个简单的队列操作模拟问题，你需要模拟出队列的基本操作（包括出队、入队、取队头等），操作命令包含如下格式：

\begin{description}
  \item[CREATE m] 创建一个最多可存储$m$个元素的队列；
  \item[DESTROY]  销毁队列，队列一旦销毁便无法再进行其他操作；
  \item[SIZE]     在一行中输出队列包含的元素个数；
  \item[ENQUEUE x]   将$x$入队，其中$x$为char类型
  \item[DEQUEUE]      队列头元素出队；
  \item[PRINTALL] 在一行中打印队列中所有元素，最左侧队头元素，最右侧为队尾元素，每个元素之间有一个空格；如果队中无元素则输出NULL；
  \item[PRINTTOP] 在一行中打印队头元素；如果队中无元素则输出NULL；队头元素不要出队；
  \item[CLEAR]    清空队中所有元素；
  \item[STOP]     终止执行命令序列；
\end{description}
\subsubsection*{输入格式}
输入包含多行，每行包含一个合法的命令；遇到\textbf{STOP}则结束。我们确保$m$的不超过1000，且命令数量不超过2000条。

\subsubsection*{输出数据格式}
对于每一个命令，模拟队列操作。对于有输出要求的命令，请按照命令的输出格式将数据输出。

\subsubsection*{输入样例}
\begin{lstlisting}[frame=none, numbers=none]
CREATE 10
ENQUEUE a
ENQUEUE b
ENQUEUE c
PRINTALL
SIZE
PRINTTOP
DEQUEUE
ENQUEUE 1
PRINTALL
DESTROY
CREATE 20
ENQUEUE a
ENQUEUE b
ENQUEUE c
ENQUEUE d
CLEAR
PRINTTOP
PRINTALL
ENQUEUE e
ENQUEUE f
ENQUEUE g
DEQUEUE
DEQUEUE
DEQUEUE
ENQUEUE 1
ENQUEUE 2
PRINTALL
DESTROY
STOP
\end{lstlisting}

\subsubsection*{输出样例}
\begin{lstlisting}[frame=none, numbers=none]
a b c
3
a
b c 1
NULL
NULL
1 2
\end{lstlisting}

\section{扩展实验题目}

\subsection{表达式的括号匹配问题}
\subsubsection*{问题描述}
Unix, Linux系统下有一款功能非常强大的计算器(数值处理语言)---bc\footnote{更多关于bc的信息，请参加http://www.gnu.org/software/bc/}。在bc中，
用户可以像编写C程序一样执行计算命令。此外，bc可以支持交互式的执行语句。例如：
\begin{verbatim}
[xgqin@localhost ~]$ bc
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'. 
i=0
sum=0
for (i=0; i<=100;++i)
{ sum += i; }
print sum, "\n"
5050
scale=6
4-2.1*(2-0.2)+1.3*(1.3+0.7)
2.82
4-2.1*(2-0.2)+1.3*((1.3+0.7)
(standard in) 9: syntax error
\end{verbatim}
如上所示，我们可使用类似C语言循环语句执行求$1+2+\ldots+100$的运算，其结果是5050；
此外还求解了$4-2.1*(2-0.2)+1.3*(1.3+0.7)$多项式的结果，其结果是$2.82$。是不是觉得bc很酷？

bc除了能执行正确的命令外，还能指明命令存在的语法错误，例如：

\verb+(standard in)9:syntax error+

指明了标准输入中第9行存在语法错误，如上最后一行所示。

当然,实现这样一个计算器需要做很多工作。目前来说,我们可以实现其中一部分 功能,即检查输入的表达式中括号是否匹配的问题。为了简化问题,我们规定输入的表达式格式满足如下:
\begin{enumerate}
  \item 表达式中只出现(, ), [, ], \{, \}等括号形式；
  \item 表达式中出现的运算符只包括+, -, *, /；
%  \item 表达式中所有运算均是整数，且均是1位正整数；
\end{enumerate}

例如,$4-\{2*(3-1)\}+5/([3-2]+(2-3))$是满足上述格式要求的表达式。你的任务是编写程序并判断这类表达式中括号是否匹配。
\subsubsection*{输入格式}
输入首先包含一个整型数T，表示有T个测试用例。接下来的每一行均表示一个测试用例，每一个测试用例格式均满足问题描述中所规定的表达式格式要求。

\subsubsection*{输出格式}
输出结果的要求非常简单，对于每一个测试用例，输入一行结果，表达式中括号匹配则输出YES，否则输出NO。

\subsubsection*{输入样例}
\begin{lstlisting}[frame=none, numbers=none]
2
4-2.1*(2-0.2)+1.3*((1.3+0.7)
4-{2*(3-1)}+5/([3-2]+(2-3))
\end{lstlisting}

\subsubsection*{输出样例}
\begin{lstlisting}[frame=none, numbers=none]
NO
YES
\end{lstlisting}

\subsection{团队队列}
\subsubsection*{问题描述}
  
  对于计算机专业而言，\textbf{队列}(Queue)和\textbf{优先队列}(Priority Queue)是大家所熟知的数据结构。然而，\textbf{团队队列}(Team Queue)则不是所有人都了解了，虽然它在日常生活中经常被会使用到。
  
  在团队队列中，每一个元素属于某一个团队(team)。当一个元素进入团队队列时，它首先查找从头至尾整个团队队列，是否有和它同属一个团队队员(teammates)。如果有的话，它将排在这些队员的后面；如果没有，它将排在团队队列的队尾。在团队队列中，元素的出队和普通的队列出队操作相同：元素从队头至队尾依次出队。
  
  你的任务是编写一个程序用于仿真团队队列的出入队操作。
  
\subsubsection*{输入格式}

  输入文件将包含一个或多个测试用例。每个测试用例以数字$t (1 \leq t \leq 1000$)开头，
  表示团队队列中团队的数量。紧接着是$t$行，分别表示$t$个队伍，每行中第一个数字表示当前队伍
  所包含的元素个数，紧接着是队伍每个元素的编号；元素的编号是整型数，且范围在$0$至$999999$之间，
  一个队伍至多包含1000个元素。
  
  最后接着是一系列的命令。命令总共包含三类：
\begin{description}
  \item[ENQUEUE $x$] 将元素$x$入团队队列；
  \item[DEQUEUE] 将团队队列的第一个元素出队；
  \item[STOP] 停止处理命令，测试用例结束；
\end{description}
  
  \textbf{注:}一个测试用例中可能包含至多$200000$个命令。因此需要考虑的实现团队队列的效率：入队及出队操作的时间均应该是常数级。
  
  
\subsubsection*{输出格式}
  对于每个测试用例，首先输出一行``\lstinline{Scenario #k}''，其中$k$是测试用例的编号。对于每一个\textbf{DEQUEUE}命令，单独一行出队的元素。每个测试用例结束后输出一个空行。

\subsubsection*{输入样例}
\begin{lstlisting}[frame=none, numbers=none]
2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
2
5 259001 259002 259003 259004 259005
6 260001 260002 260003 260004 260005 260006
ENQUEUE 259001
ENQUEUE 260001
ENQUEUE 259002
ENQUEUE 259003
ENQUEUE 259004
ENQUEUE 259005
DEQUEUE
DEQUEUE
ENQUEUE 260002
ENQUEUE 260003
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0
\end{lstlisting}

\subsubsection*{输出样例}
\begin{lstlisting}[frame=none, numbers=none]
Scenario #1
101
102
103
201
202
203

Scenario #2
259001
259002
259003
259004
259005
260001

\end{lstlisting}

\subsection{火车进站出站问题 goj1070}

\subsubsection*{问题描述}
有$n$节车厢从A方向驶入车站，按进站顺序编号为1$\sim$n,为了重组车厢需要借助中转站C，
中转站C可以让你停放任意多节车厢，但由于末端封顶，驶入C的车厢必须按相反的顺序驶出C。
对于每个车厢，只能由A向C驶入且不能由C向A驶出以及只能由C向B驶出且不能由B向C驶入。
现在给驶入的车厢数量和驶出B的车厢顺序，判断车厢是否能够按给出的车厢顺序驶出，如图\ref{fig:train}所示。

\begin{figure}[thp]
  \label{fig:train}
  \centering
  \caption{火车进出站轨道}
  \includegraphics[width=0.8\textwidth]{images/ch03/goj-1070.png}
\end{figure}

\subsubsection*{输入格式}
输入包含多个测试用例，每个测试用例由2行组成，第1行是一个整型数n，表示车厢数。接下来一行有n个整型数，每个数用空格作为间隔，表示车厢驶出的顺序。

\subsubsection*{输出格式}
对于每一个测试用例，输出一行。当能按照给定顺序驶出的，请输出Yes，否则输出No（第一个字母需大写）

\subsubsection*{输入样例}
\begin{lstlisting}[frame=none, numbers=none]
5
3 2 4 1 5
5
3 1 2 5 4
\end{lstlisting}

\subsubsection*{输出样例}
\begin{lstlisting}[frame=none, numbers=none]
Yes
No
\end{lstlisting}


